package structure;

import java.util.*;

public class Test9 {
    //leetcode 236 二叉树的最近公共祖先(法1-DFS)
    class Solution0 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode node = findTreeNode(root,p,q);
            return node;
        }
        public TreeNode findTreeNode(TreeNode root, TreeNode p, TreeNode q){
            if(root == null || root == p || root == q){
                return root;
            }
            TreeNode left = findTreeNode(root.left,p,q);
            TreeNode right = findTreeNode(root.right,p,q);
            if(left != null && right != null){
                return root;
            }
            if(left != null){
                return left;
            }
            if(right != null){
                return right;
            }
            return null;
        }
    }
    //leetcode 236 二叉树的最近公共祖先(法2-辅助栈)
    class Solution2 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            Deque<TreeNode> deque1 = new LinkedList<>();
            Deque<TreeNode> deque2 = new LinkedList<>();
            findNode(root, p, deque1);
            findNode(root, q, deque2);
            int len1 = deque1.size();
            int len2 = deque2.size();
            int size = 0;
            if (len1 > len2) {
                size = len1 - len2;
                while (size-- > 0) {
                    deque1.pop();
                }
            } else if (len1 < len2) {
                size = len2 - len1;
                while (size-- > 0) {
                    deque2.pop();
                }
            }
            while (deque1.peek() != deque2.peek()) {
                deque1.pop();
                deque2.pop();
            }
            return deque1.peek();
        }

        public boolean findNode(TreeNode root, TreeNode cur, Deque<TreeNode> deque) {
            if (root == null) {
                return false;
            }
            deque.push(root);
            if (root == cur) {
                return true;
            }
            boolean left = findNode(root.left, cur, deque);
            if (left == true) {
                return true;
            }
            boolean right = findNode(root.right, cur, deque);
            if (right == true) {
                return true;
            }
            deque.pop();
            return false;
        }
    }
    //牛客 二叉树遍历(较难)
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }
    public class Main {
        public static int i;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String str = in.next();
            TreeNode root = createTree(str);
            display(root);
        }

        public static TreeNode createTree(String str){
            char c = str.charAt(i++);
            if(c == '#'){
                return null;
            }
            TreeNode root = new TreeNode(c);
            root.left = createTree(str);
            root.right = createTree(str);
            return root;
        }

        public static void display(TreeNode root){
            if(root == null){
                return;
            }
            display(root.left);
            System.out.print(root.val + " ");
            display(root.right);
        }
    }
}